/*-------------------------------------------------------------------------
 *
 * ts_selfuncs.c
 *	  文本搜索操作符的选择性估计函数。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/tsearch/ts_selfuncs.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/htup_details.h"
#include "catalog/pg_statistic.h"
#include "catalog/pg_type.h"
#include "miscadmin.h"
#include "nodes/nodes.h"
#include "tsearch/ts_type.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"


/*
 * 默认的文本搜索选择性被选择得足够小，以
 * 鼓励对典型表密度的索引扫描。详见selfuncs.h和
 * DEFAULT_EQ_SEL。
 */
#define DEFAULT_TS_MATCH_SEL 0.005

/* 用于通过MCELEMs进行二进制搜索的查找表类型 */
typedef struct
{
	text	   *element;
	float4		frequency;
} TextFreq;

/* 用于在TextFreqs数组中进行bsearch的键类型 */
typedef struct
{
	char	   *lexeme;
	int			length;
} LexemeKey;

static Selectivity fc_tsquerysel(VariableStatData *fc_vardata, Datum fc_constval);
static Selectivity fc_mcelem_tsquery_selec(TSQuery fc_query,
										Datum *fc_mcelem, int fc_nmcelem,
										float4 *fc_numbers, int fc_nnumbers);
static Selectivity fc_tsquery_opr_selec(QueryItem *fc_item, char *fc_operand,
									 TextFreq *fc_lookup, int fc_length, float4 fc_minfreq);
static int	fc_compare_lexeme_textfreq(const void *fc_e1, const void *fc_e2);

#define tsquery_opr_selec_no_stats(query) \
	fc_tsquery_opr_selec(GETQUERY(query), GETOPERAND(query), NULL, 0, 0)


/*
 *	tsmatchsel -- "@@" 的选择性
 *
 * tsvector @@ tsquery 和
 * tsquery @@ tsvector 的限制选择性函数
 */
Datum tsmatchsel(PG_FUNCTION_ARGS)
{
	PlannerInfo *fc_root = (PlannerInfo *) PG_GETARG_POINTER(0);

#ifdef NOT_USED
	Oid			fc_operator = PG_GETARG_OID(1);
#endif
	List	   *fc_args = (List *) PG_GETARG_POINTER(2);
	int			fc_varRelid = PG_GETARG_INT32(3);
	VariableStatData fc_vardata;
	Node	   *fc_other;
	bool		fc_varonleft;
	Selectivity fc_selec;

	/*
	 * 如果表达式不是变量 = 某个值或某个值 = 变量，则
	 * 直接返回默认估计。
	 */
	if (!get_restriction_variable(fc_root, fc_args, fc_varRelid,
								  &fc_vardata, &fc_other, &fc_varonleft))
		PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);

	/*
	 * 如果 something 也不是常量，就无法做任何有用的事情。
	 */
	if (!IsA(fc_other, Const))
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
	}

	/*
	 * "@@" 运算符是严格的，因此我们可以立即处理NULL
	 */
	if (((Const *) fc_other)->constisnull)
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(0.0);
	}

	/*
	 * 好吧，我们这里处理的是一个Var和一个Const。我们需要
	 * Const是一个TSQuery，否则我们无法做任何有用的事情。我们必须
	 * 检查这一点，因为Var可能是TSQuery而不是TSVector。
	 */
	if (((Const *) fc_other)->consttype == TSQUERYOID)
	{
		/* tsvector @@ tsquery 或反之亦然 */
		Assert(fc_vardata.vartype == TSVECTOROID);

		fc_selec = fc_tsquerysel(&fc_vardata, ((Const *) fc_other)->constvalue);
	}
	else
	{
		/* 如果我们无法看到查询结构，必须放弃 */
		fc_selec = DEFAULT_TS_MATCH_SEL;
	}

	ReleaseVariableStats(fc_vardata);

	CLAMP_PROBABILITY(fc_selec);

	PG_RETURN_FLOAT8((float8) fc_selec);
}


/*
 *	tsmatchjoinsel -- "@@" 的连接选择性
 *
 * tsvector @@ tsquery 和 tsquery @@ tsvector 的连接选择性函数
 */
Datum tsmatchjoinsel(PG_FUNCTION_ARGS)
{
	/* 目前我们只好放弃 */
	PG_RETURN_FLOAT8(DEFAULT_TS_MATCH_SEL);
}


/*
 * tsvector变量与tsquery常量的@@选择性
 */
static Selectivity fc_tsquerysel(VariableStatData *fc_vardata, Datum fc_constval)
{
	Selectivity fc_selec;
	TSQuery		fc_query;

	/* 调用者确保常量是TSQuery，现在获取它 */
	fc_query = DatumGetTSQuery(fc_constval);

	/* 空查询不匹配任何内容 */
	if (fc_query->size == 0)
		return (Selectivity) 0.0;

	if (HeapTupleIsValid(fc_vardata->statsTuple))
	{
		Form_pg_statistic fc_stats;
		AttStatsSlot fc_sslot;

		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata->statsTuple);

		/* MCELEM将是tsvector列的TEXT元素数组 */
		if (get_attstatsslot(&fc_sslot, fc_vardata->statsTuple,
							 STATISTIC_KIND_MCELEM, InvalidOid,
							 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
		{
			/*
			 * tsvector Var有一个最常见元素槽，因此
			 * 使用它。
			 */
			fc_selec = fc_mcelem_tsquery_selec(fc_query, fc_sslot.values, fc_sslot.nvalues,
										 fc_sslot.numbers, fc_sslot.nnumbers);
			free_attstatsslot(&fc_sslot);
		}
		else
		{
			/* 没有最常见元素信息，因此不使用 */
			fc_selec = tsquery_opr_selec_no_stats(fc_query);
		}

		/*
		 * MCE统计信息只计算非NULL行，因此要调整NULL行。
		 */
		fc_selec *= (1.0 - fc_stats->stanullfrac);
	}
	else
	{
		/* 完全没有统计信息，因此不使用 */
		fc_selec = tsquery_opr_selec_no_stats(fc_query);
		/* 我们假设这里没有NULL，因此没有stanullfrac校正 */
	}

	return fc_selec;
}

/*
 * 从pg_statistic数组中提取数据到有用的格式。
 */
static Selectivity fc_mcelem_tsquery_selec(TSQuery fc_query, Datum *fc_mcelem, int fc_nmcelem,
					 float4 *fc_numbers, int fc_nnumbers)
{
	float4		fc_minfreq;
	TextFreq   *fc_lookup;
	Selectivity fc_selec;
	int			fc_i;

	/*
	 * 应该有比值多两个数字，因为最后两个
	 * 单元用于最小和最大频率。如果没有则放弃。
	 *
	 * （注意：MCELEM统计信息槽的定义允许一个额外的
	 * 数字包含NULL的频率，但我们不期望在
	 * tsvector列中出现。）
	 */
	if (fc_nnumbers != fc_nmcelem + 2)
		return tsquery_opr_selec_no_stats(fc_query);

	/*
	 * 将数据转置为一个数组，以便我们可以使用bsearch()。
	 */
	fc_lookup = (TextFreq *) palloc(sizeof(TextFreq) * fc_nmcelem);
	for (fc_i = 0; fc_i < fc_nmcelem; fc_i++)
	{
		/*
		 * 文本Datums来自一个数组，因此它不能被压缩或
		 * 存储在线外——使用 VARSIZE_ANY* 是安全的。
		 */
		Assert(!VARATT_IS_COMPRESSED(fc_mcelem[fc_i]) && !VARATT_IS_EXTERNAL(fc_mcelem[fc_i]));
		fc_lookup[fc_i].element = (text *) DatumGetPointer(fc_mcelem[fc_i]);
		fc_lookup[fc_i].frequency = fc_numbers[fc_i];
	}

	/*
	 * 获取最低频率。compute_tsvector_stats()将其存储在
	 * 数字数组的倒数第二个单元中。见 ts_typanalyze.c
	 */
	fc_minfreq = fc_numbers[fc_nnumbers - 2];

	fc_selec = fc_tsquery_opr_selec(GETQUERY(fc_query), GETOPERAND(fc_query), fc_lookup,
							  fc_nmcelem, fc_minfreq);

	pfree(fc_lookup);

	return fc_selec;
}

/*
 * 前序遍历 tsquery，计算选择性如下：
 *
 *	 selec(left_oper) * selec(right_oper) 在 AND 和 PHRASE 节点中，
 *
 *	 selec(left_oper) + selec(right_oper) -
 *		selec(left_oper) * selec(right_oper) 在 OR 节点中，
 *
 *	 1 - select(oper) 在 NOT 节点中
 *
 *	 基于直方图的估计在前缀 VAL 节点中
 *
 *	 freq[val] 在精确 VAL 节点中，如果值在 MCELEM 中
 *	 min(freq[MCELEM]) / 2 在 VAL 节点中，如果不在
 *
 * MCELEM 数组已经排序（见 ts_typanalyze.c），因此我们可以使用
 * 二分搜索来确定 freq[MCELEM]。
 *
 * 如果我们没有 tsvector 的统计信息，我们仍然使用这个逻辑，
 * 只是对于 VAL 节点使用默认估计。这个情况由 lookup == NULL 表示。
 */
static Selectivity fc_tsquery_opr_selec(QueryItem *fc_item, char *fc_operand,
				  TextFreq *fc_lookup, int fc_length, float4 fc_minfreq)
{
	Selectivity fc_selec;

	/* 由于这个函数递归，可能会导致栈溢出 */
	check_stack_depth();

	if (fc_item->type == QI_VAL)
	{
		QueryOperand *fc_oper = (QueryOperand *) fc_item;
		LexemeKey	fc_key;

		/*
		 * 准备 bsearch() 的键。
		 */
		fc_key.lexeme = fc_operand + fc_oper->distance;
		fc_key.length = fc_oper->length;

		if (fc_oper->prefix)
		{
			/* 前缀匹配，即查询项为 lexeme:* */
			Selectivity fc_matched,
						fc_allmces;
			int			fc_i,
						fc_n_matched;

			/*
			 * 我们的策略是扫描 MCELEM 列表并结合匹配前缀的
			 * 频率。然后我们推测匹配的 MCELEM 的比例至其余行，
			 * 假设 MCELEM 在这方面代表整个词素种群。 （比较
			 * histogram_selectivity()。）注意这些是最常见的
			 * 元素，而不是最常见的值，所以它们不是互斥的。
			 * 我们将发生的情况视为独立事件。
			 *
			 * 只有在我们有相当数量的 MCELEM 时，这才是一个好计划；
			 * 我们将阈值设为 100。如果没有统计信息或
			 * 统计信息不足，则任意使用 DEFAULT_TS_MATCH_SEL*4。
			 */
			if (fc_lookup == NULL || fc_length < 100)
				return (Selectivity) (DEFAULT_TS_MATCH_SEL * 4);

			fc_matched = fc_allmces = 0;
			fc_n_matched = 0;
			for (fc_i = 0; fc_i < fc_length; fc_i++)
			{
				TextFreq   *fc_t = fc_lookup + fc_i;
				int			fc_tlen = VARSIZE_ANY_EXHDR(fc_t->element);

				if (fc_tlen >= fc_key.length &&
					strncmp(fc_key.lexeme, VARDATA_ANY(fc_t->element),
							fc_key.length) == 0)
				{
					fc_matched += fc_t->frequency - fc_matched * fc_t->frequency;
					fc_n_matched++;
				}
				fc_allmces += fc_t->frequency - fc_allmces * fc_t->frequency;
			}

			/* 限制以确保在舍入误差面前的合理性 */
			CLAMP_PROBABILITY(fc_matched);
			CLAMP_PROBABILITY(fc_allmces);

			fc_selec = fc_matched + (1.0 - fc_allmces) * ((double) fc_n_matched / fc_length);

			/*
			 * 在任何情况下，永远不要相信前缀匹配的选择性
			 * 小于我们为非 MCELEM 词素分配的选择性。
			 * 这保证了“word:*”的估计应该
			 * 至少匹配与“word”相同的行数。
			 */
			fc_selec = Max(Min(DEFAULT_TS_MATCH_SEL, fc_minfreq / 2), fc_selec);
		}
		else
		{
			/* 常规精确词素匹配 */
			TextFreq   *fc_searchres;

			/* 如果变量没有统计信息，使用 DEFAULT_TS_MATCH_SEL */
			if (fc_lookup == NULL)
				return (Selectivity) DEFAULT_TS_MATCH_SEL;

			fc_searchres = (TextFreq *) bsearch(&fc_key, fc_lookup, fc_length,
											 sizeof(TextFreq),
											 fc_compare_lexeme_textfreq);

			if (fc_searchres)
			{
				/*
				 * 元素在 MCELEM 中。返回精确的选择性（或
				 * 至少与 ANALYZE 能找到的一样精确）。
				 */
				fc_selec = fc_searchres->frequency;
			}
			else
			{
				/*
				 * 元素不在 MCELEM 中。放弃，但假设选择性
				 * 不超过 minfreq / 2。
				 */
				fc_selec = Min(DEFAULT_TS_MATCH_SEL, fc_minfreq / 2);
			}
		}
	}
	else
	{
		/* 当前 TSQuery 节点是一个操作符 */
		Selectivity fc_s1,
					fc_s2;

		switch (fc_item->qoperator.oper)
		{
			case OP_NOT:
				fc_selec = 1.0 - fc_tsquery_opr_selec(fc_item + 1, fc_operand,
												fc_lookup, fc_length, fc_minfreq);
				break;

			case OP_PHRASE:
			case OP_AND:
				fc_s1 = fc_tsquery_opr_selec(fc_item + 1, fc_operand,
									   fc_lookup, fc_length, fc_minfreq);
				fc_s2 = fc_tsquery_opr_selec(fc_item + fc_item->qoperator.left, fc_operand,
									   fc_lookup, fc_length, fc_minfreq);
				fc_selec = fc_s1 * fc_s2;
				break;

			case OP_OR:
				fc_s1 = fc_tsquery_opr_selec(fc_item + 1, fc_operand,
									   fc_lookup, fc_length, fc_minfreq);
				fc_s2 = fc_tsquery_opr_selec(fc_item + fc_item->qoperator.left, fc_operand,
									   fc_lookup, fc_length, fc_minfreq);
				fc_selec = fc_s1 + fc_s2 - fc_s1 * fc_s2;
				break;

			default:
				elog(ERROR, "unrecognized operator: %d", fc_item->qoperator.oper);
				fc_selec = 0;		/* 保持编译器安静 */
				break;
		}
	}

	/* 将中间结果限制在合理范围内，以避免舍入误差 */
	CLAMP_PROBABILITY(fc_selec);

	return fc_selec;
}

/*
 * bsearch() 的比较器，用于词素（非 NULL 终止字符串和长度） 
 * 和 TextFreq。先使用长度，然后逐字节比较，因为这就是
 * ANALYZE 代码在将数据存储到统计元组之前排序数据的方式。
 * 详细信息见 ts_typanalyze.c。
 */
static int fc_compare_lexeme_textfreq(const void *fc_e1, const void *fc_e2)
{
	const LexemeKey *fc_key = (const LexemeKey *) fc_e1;
	const TextFreq *fc_t = (const TextFreq *) fc_e2;
	int			fc_len1,
				fc_len2;

	fc_len1 = fc_key->length;
	fc_len2 = VARSIZE_ANY_EXHDR(fc_t->element);

	/* 先比较长度，可能避免 strncmp 调用 */
	if (fc_len1 > fc_len2)
		return 1;
	else if (fc_len1 < fc_len2)
		return -1;

	/* 退回到逐字节比较 */
	return strncmp(fc_key->lexeme, VARDATA_ANY(fc_t->element), fc_len1);
}
